// 版权归Go作者所有。版权所有。
// 此源代码的使用受BSD样式
// 许可证的约束，该许可证可以在许可证文件中找到。

package runtime

import (
	"runtime/internal/sys"
)

// pageBits是一个位图，表示palloc块中每页一位。
type pageBits [pallocChunkPages / 64]uint64

// get返回位图中第i位的值。
func (b *pageBits) get(i uint) uint {
	return uint((b[i/64] >> (i % 64)) & 1)
}

// block64返回包含第i位的64位对齐位块。
func (b *pageBits) block64(i uint) uint64 {
	return b[i/64]
}

// 设置页位的位i。
func (b *pageBits) set(i uint) {
	b[i/64] |= 1 << (i % 64)
}

// 设置范围[i，i+n]中的位。
func (b *pageBits) setRange(i, n uint) {
	_ = b[i/64]
	if n == 1 {
		// n==1的快速路径。
		b.set(i)
		return
	}
	// 设置位[i，j].
	j := i + n - 1
	if i/64 == j/64 {
		b[i/64] |= ((uint64(1) << n) - 1) << (i % 64)
		return
	}
	_ = b[j/64]
	// 设置前导位。
	b[i/64] |= ^uint64(0) << (i % 64)
	for k := i/64 + 1; k < j/64; k++ {
		b[k] = ^uint64(0)
	}
	// 设置尾随位。
	b[j/64] |= (uint64(1) << (j%64 + 1)) - 1
}

// setAll设置b的所有位。
func (b *pageBits) setAll() {
	for i := range b {
		b[i] = ^uint64(0)
	}
}

// 清除页位的位i。
func (b *pageBits) clear(i uint) {
	b[i/64] &^= 1 << (i % 64)
}

// 清除范围[i，i+n]中的位。
func (b *pageBits) clearRange(i, n uint) {
	_ = b[i/64]
	if n == 1 {
		// n==1情况的快速路径。
		b.clear(i)
		return
	}
	// 清除位[i，j].
	j := i + n - 1
	if i/64 == j/64 {
		b[i/64] &^= ((uint64(1) << n) - 1) << (i % 64)
		return
	}
	_ = b[j/64]
	// 清除前导位。
	b[i/64] &^= ^uint64(0) << (i % 64)
	for k := i/64 + 1; k < j/64; k++ {
		b[k] = 0
	}
	// 清除尾随位。
	b[j/64] &^= (uint64(1) << (j%64 + 1)) - 1
}

// clearAll释放b的所有位。
func (b *pageBits) clearAll() {
	for i := range b {
		b[i] = 0
	}
}

// popcntRange统计
// 范围内的设置位数[i，i+n）.
func (b *pageBits) popcntRange(i, n uint) (s uint) {
	if n == 1 {
		return uint((b[i/64] >> (i % 64)) & 1)
	}
	_ = b[i/64]
	j := i + n - 1
	if i/64 == j/64 {
		return uint(sys.OnesCount64((b[i/64] >> (i % 64)) & ((1 << n) - 1)))
	}
	_ = b[j/64]
	s += uint(sys.OnesCount64(b[i/64] >> (i % 64)))
	for k := i/64 + 1; k < j/64; k++ {
		s += uint(sys.OnesCount64(b[k]))
	}
	s += uint(sys.OnesCount64(b[j/64] & ((1 << (j%64 + 1)) - 1)))
	return
}

// pallocBits是一个位图，它最多跟踪一个
// palloc chunk的页面分配。
// 
// 精确表示是一个实现细节，但对于
// 为了文档的缘故，0是免费页面，1是分配页面。
type pallocBits pageBits

// summary返回位图的压缩摘要（以pallocBits为单位）。
func (b *pallocBits) summarize() pallocSum {
	var start, max, cur uint
	const notSetYet = ^uint(0) // 开始值的sentinel 
	start = notSetYet
	for i := 0; i < len(b); i++ {
		x := b[i]
		if x == 0 {
			cur += 64
			continue
		}
		t := uint(sys.TrailingZeros64(x))
		l := uint(sys.LeadingZeros64(x))

		// 完成跨uint64s 
		cur += t
		if start == notSetYet {
			start = cur
		}
		if cur > max {
			max = cur
		}
		// 可能跨到下一个uint64 
		cur = l
	}
	if start == notSetYet {
		// 一路通过，但没有找到一个1位。
		const n = uint(64 * len(b))
		return packPallocSum(n, n, n)
	}
	if cur > max {
		max = cur
	}
	if max >= 64-2 {
		// 有我s内部零的运行不可能超过max.
		return packPallocSum(start, max, cur)
	}
	// 现在查看每个单元64中的零运行情况。
	// 所有单元64必须为非零，否则我们将在上面中止。
outer:
	for i := 0; i < len(b); i++ {
		x := b[i]

		// 查看此单元64。我们有一个类似于
		// 0000001xxxxx1000000 
		// 的模式，我们需要查看1xxxxx1内部是否有任何连续的
		// 零区域。

		// 我们已经知道尾随的零不大于最大值。将其删除。
		x >>= sys.TrailingZeros64(x) & 63
		if x&(x+1) == 0 { // 不再有零（顶部除外）.
			continue
		}

		// 策略：将所有零运行的最大值缩减。如果任何零运行的最大值
		// 仍然存在，那么我们已经确定了一个更大的最大零运行。
		p := max     // 我们仍然需要缩减的零数量。
		k := uint(1) // 当前x中1的最小运行长度。
		for {
			// 将所有零运行的最大值缩减为p位（除顶部零位）。
			for p > 0 {
				if p <= k {
					// 将p位下移到每一次零位的顶部。
					x |= x >> (p & 63)
					if x&(x+1) == 0 { // 不再有零位（除顶部外）。
						continue outer
					}
					break
				}
				// 将k位下移到每一次零位的顶部。
				x |= x >> (k & 63)
				if x&(x+1) == 0 { // 不再有零位（除顶部外）.
					continue outer
				}
				p -= k
				// 我们刚刚将1次运行的最小长度增加了一倍。
				// 这允许我们在下一次迭代中进一步移动。
				k *= 2
			}

			// 最低阶零次运行的长度是最大值的增量。
			j := uint(sys.TrailingZeros64(^x)) // 计算连续的后续运行
			x >>= j & 63                       // 删除后续运行
			j = uint(sys.TrailingZeros64(x))   // 计算连续的尾随零
			x >>= j & 63                       // 删除零
			max += j                           // 我们有了一个新的最大值！
			if x&(x+1) == 0 {                  // 不再有零（顶部除外）.
				continue outer
			}
			p = j // 从每次零运行中再删除j个零。
		}
	}
	return packPallocSum(start, max, cur)
}

// 查找pallocBits中的npages连续可用页并返回
// 运行开始的索引，以及在搜索中找到的第一个可用页的索引
// searchIdx表示第一个已知的可用页和
// 从何处开始下一次搜索。
// 
// 如果find未能找到任何可用空间，则返回^uint（0）索引和
// 应该忽略新的searchIdx。
// 
// 请注意，如果npages==1，两个返回值将始终相同。
func (b *pallocBits) find(npages uintptr, searchIdx uint) (uint, uint) {
	if npages == 1 {
		addr := b.find1(searchIdx)
		return addr, addr
	} else if npages <= 64 {
		return b.findSmallN(npages, searchIdx)
	}
	return b.findLargeN(npages, searchIdx)
}

// find1是find的助手，它在pallocBits中搜索单个空闲页并返回索引。
// 
// 有关searchIdx参数的解释，请参见find。
func (b *pallocBits) find1(searchIdx uint) uint {
	_ = b[0] // lift nil check out loop 
	for i := searchIdx / 64; i < uint(len(b)); i++ {
		x := b[i]
		if ^x == 0 {
			continue
		}
		return i*64 + uint(sys.TrailingZeros64(^x))
	}
	return ^uint(0)
}

// findSmallN是find的助手，它在这个pallocBits中搜索npages连续可用页
// 并返回连续页运行
// 开始的索引l作为它在搜索中找到的第一个免费页面的索引。
// 
// 有关searchIdx参数的解释，请参阅find。
// 
// 失败时返回^uint（0）索引，应忽略新的searchIdx。
// 
// findSmallN假设npages<=64，其中任何这样连续的页面运行
// 在位中最多跨越一个对齐的64位边界。
func (b *pallocBits) findSmallN(npages uintptr, searchIdx uint) (uint, uint) {
	end, newSearchIdx := uint(0), ^uint(0)
	for i := searchIdx / 64; i < uint(len(b)); i++ {
		bi := b[i]
		if ^bi == 0 {
			end = 0
			continue
		}
		// 首先看看我们是否可以将分配打包到后面的
		// 0加上最后64位的末尾。
		if newSearchIdx == ^uint(0) {
			// 新的searchIdx将位于我们文件中的任何
			// 1之后的64位，所以计算后面的1。
			newSearchIdx = i*64 + uint(sys.TrailingZeros64(^bi))
		}
		start := uint(sys.TrailingZeros64(bi))
		if end+start >= uint(npages) {
			return i*64 - end, newSearchIdx
		}
		// 接下来，检查64位块的内部。
		j := findBitRange64(^bi, uint(npages))
		if j < 64 {
			return i*64 + j, newSearchIdx
		}
		end = uint(sys.LeadingZeros64(bi))
	}
	return ^uint(0), newSearchIdx
}

// findLargeN是find的助手，它在这个pallocBits中搜索npages连续可用页
// 并返回运行开始的索引，以及在搜索中找到的第一个可用页的索引。
// 
// 有关searchIdx参数的说明，请参阅alloc。
// 
// 失败时返回^uint（0）索引，应忽略新的searchIdx。
// 
// findLargeN假设npages>64，其中任何这样的空闲页运行
// 在位中至少跨越一个对齐的64位边界。
func (b *pallocBits) findLargeN(npages uintptr, searchIdx uint) (uint, uint) {
	start, size, newSearchIdx := ^uint(0), uint(0), ^uint(0)
	for i := searchIdx / 64; i < uint(len(b)); i++ {
		x := b[i]
		if x == ^uint64(0) {
			size = 0
			continue
		}
		if newSearchIdx == ^uint(0) {
			// 新的searchIdx将位于我们文件中任何
			// 1之后的64位，所以计算后面的1。
			newSearchIdx = i*64 + uint(sys.TrailingZeros64(^x))
		}
		if size == 0 {
			size = uint(sys.LeadingZeros64(x))
			start = i*64 + 64 - size
			continue
		}
		s := uint(sys.TrailingZeros64(x))
		if s+size >= uint(npages) {
			size += s
			return start, newSearchIdx
		}
		if s < 64 {
			size = uint(sys.LeadingZeros64(x))
			start = i*64 + 64 - size
			continue
		}
		size += 64
	}
	if size < uint(npages) {
		return ^uint(0), newSearchIdx
	}
	return start, newSearchIdx
}

// allocRange分配范围[i，i+n]。
func (b *pallocBits) allocRange(i, n uint) {
	(*pageBits)(b).setRange(i, n)
}

// allocAll分配b的所有位。
func (b *pallocBits) allocAll() {
	(*pageBits)(b).setAll()
}

// free1在pallocBits中释放一个页面。
func (b *pallocBits) free1(i uint) {
	(*pageBits)(b).clear(i)
}

// free释放范围pallocBits中的[i，i+n]页。
func (b *pallocBits) free(i, n uint) {
	(*pageBits)(b).clearRange(i, n)
}

// freeAll释放b的所有位。
func (b *pallocBits) freeAll() {
	(*pageBits)(b).clearAll()
}

// pages64返回一个64位位图，表示一个由64页组成的块，该块与
// 64页对齐。返回的页面块包含此pallocBits中的第i个
// 页。每个位表示是否页面正在使用中。
func (b *pallocBits) pages64(i uint) uint64 {
	return (*pageBits)(b).block64(i)
}

// findBitRange64返回第一组
// n连续1位的位索引。如果在c中找不到连续1位的
// n，则返回一个大于等于64的整数。
// n必须大于0。
func findBitRange64(c uint64, n uint) uint {
	// 此实现基于shrinking连续1位运行的
	// 长度。我们从每个1的运行中删除前n-1个1位
	// 然后查找剩余的第一个1位。
	p := n - 1   // 我们要删除的1的数量。
	k := uint(1) // c中当前最小运行宽度为0。
	for p > 0 {
		if p <= k {
			// 将p 0s向下移到0的顶部每次运行1s.
			c &= c >> (p & 63)
			break
		}
		// 将k0向下移动到每次运行1s的顶部。
		c &= c >> (k & 63)
		if c == 0 {
			return 64
		}
		p -= k
		// 我们刚刚将0次运行的最小长度增加了一倍。
		// 这允许我们在下一次迭代中进一步移动。
		k *= 2
	}
	// 找到剩余的第一个1。
	// 因为我们从顶部向下收缩，第一个1位于
	// 其正确的原始位置。
	return uint(sys.TrailingZeros64(c))
}

// pallocData封装pallocBits和
// 的位图。是否在单个
// 结构中清除给定页面。它实际上是一个具有
// 附加功能的pallocBits。
// 
// 结构更改。
type pallocData struct {
	pallocBits
	scavenged pageBits
}

// allocRange设置位位图中的[i，i+n]为1，
// 适当更新清除的位。
func (m *pallocData) allocRange(i, n uint) {
	// 在分配范围时清除清除的位。
	m.pallocBits.allocRange(i, n)
	m.scavenged.clearRange(i, n)
}

// allocAll将位图中的每个位设置为1，并适当更新
// 在分配范围时清除的位。
func (m *pallocData) allocAll() {
	// 在分配范围时清除清除清除的位分配范围。
	m.pallocBits.allocAll()
	m.scavenged.clearAll()
}
